package sort;
/*
 *ClassName:Test
 *Description:
 *@author:可爱的大鸭子
 */

import java.util.Arrays;

public class Test {
    static int []arr={5,2,3,4,9,8,7,6,1};
    public static void Swap(int a,int b){
        a+=b;
        b=a-b;
        a=a-b;
    }
    /*冒泡*/
    public static void BubSort(int arr[],int len){
        for(int i=0;i<len-1;i++){
            for(int j=len-1;j>i;j--){
                if(arr[j]<arr[j-1]){
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
    }
    /*冒泡优化*/
    public static void BubSort1(int arr[],int len){
        for(int i=0;i<len-1;i++){
            boolean flag=false;
            for(int j=len-1;j>i;j--){
                if(arr[j]<arr[j-1]){
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    flag=true;
                }
                if(flag=false) break;
            }
        }
    }

    /*选择*/
    public static void SelSort(int arr[],int len){
        for(int i = 0;i < len - 1;i++){
            int lowindex = i;   //每次都假设最小数据的位置在第一个
            for(int j = i + 1;j < len;j++)
                if(arr[j] < arr[lowindex])
                    lowindex = j;
            Swap(arr[i],arr[lowindex]);//把最小数据放在前面
        }
    }

    /*插入*/
    public static void InsSort(int arr[],int len){
        //首先开始第0个位置是有序的
        for(int i = 1;i < len;i++) {
            for (int j = i; j >= 1 && arr[j] < arr[j - 1]; j--) {        //每次在子序列中找插入的位置
                Swap(arr[j],arr[j-1]);
                int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
    }

    /*快速*/
    //1.两个指针一前一后逐步向后扫描的方法
    public static int Partition(int arr[],int i,int j)
    {
        //这里选择尾元素作为轴值,轴值的选择可以设计为一个函数
        //如果选择的轴值不是尾元素，还需将轴值与尾元素交换
        int pivot = arr[j];
        int l = i - 1;
        for(int r = i;r < j;r++)
            if(arr[r] <= pivot)
                Swap(arr[++l],arr[r]);
        Swap(arr[++l],arr[j]);//将轴值从末尾与++l位置的元素交换
        return l;
    }

    //2.两个下标分别从首尾向中间扫描的方法
    public static int Partition1(int arr[],int low,int high){
        int pivot=arr[low];			//取当前表的第一个元素为枢轴值，对表进行划分
        while(low<high){			//循环跳出条件
            while(low<high&&arr[high]>=pivot)	--high;
            arr[low]=arr[high];			//将比枢轴值小的元素移动到左端
            while(low<high&&arr[low]<=pivot)	++low;
            arr[high]=arr[low];			//将比枢轴值大的元素移动到右端
        }
        arr[low]=pivot;
        return low;					//返回枢轴的最终位置
    }

    public static void QuickSort(int arr[],int i,int j)
    {
        if(j <= i)  return;
        int p = Partition(arr,i,j);
        QuickSort(arr,i,p - 1);
        QuickSort(arr,p + 1,j);
    }


    public static void main(String[] args) {
        //BubSort1(arr,arr.length);
        InsSort(arr,arr.length);
        for(int i:arr)
            System.out.print(i);
    }
}
